﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Maps;
using Algoritmia.DataStructures.Sets;
using Algoritmia.Schemes;
using Algoritmia.StateSpaces;
using Algoritmia.Utils;
using Sets = Algoritmia.DataStructures.Sets;

namespace Algoritmia.Problems.PerfectHash.Cichelli
{
    public class PerfectHashStateSpace3 : IReversibleForwardStateSpace<PerfectHashStateSpace3.State, Tuple<int, int, int>>
    {
        public class State
        {
            private readonly int _maxValue;
            private readonly Func<IMap<char, int>> _createMap;
            private readonly Func<Sets.ISet<int>> _createSetOfIntegers;

            public List<char> FoundChars { get; private set; }
            public readonly List<string> Words;
            public Sets.ISet<int> UsedValues { get; private set; }
            public int Index;
            public readonly List<char> Chars;
            public IMap<char, int> G { get; private set; }

            public State(IEnumerable<string> words, int maxValue, Func<IMap<char, int>> createMap = null, Func<Sets.ISet<int>> createSetOfIntegers = null)
            {
                _createMap = createMap ?? (() => AlgoritmiaFactory.Maps<char, int>.Default);
                _createSetOfIntegers = createSetOfIntegers ?? (() => new IntSet(capacity: _maxValue + 1));
                Words = words.ToList();
                _maxValue = maxValue;
                Chars = (from w in words
                         select w[0]).Union(from w in words
                                            select w.Last()).ToList();
                G = _createMap();
                Index = 0;

                FoundChars = new[] { Words[0][0], Words[0].Last() }.Distinct().ToList();
                for (int i = 1; i < Words.Count; i++)
                {
                    FoundChars.AddRange(new[] { Words[i][0], Words[i].Last() }.Distinct());
                }
                UsedValues = _createSetOfIntegers();
            }
        }

        private readonly List<string> _words;
        private readonly int _maxValue;

        public PerfectHashStateSpace3(IEnumerable<string> words, int maxValue)
        {
            _words = words.ToList();
            _maxValue = maxValue;
            var freq = AlgoritmiaFactory.Maps<char, int>.Default;
            foreach (var w in _words)
            {
                freq[w[0]] = freq.Get(w[0], 0) + 1;
                freq[w.Last()] = freq.Get(w.Last(), 0) + 1;
            }

            _words.Sort((a, b) =>
                            {
                                var fa = freq[a[0]] + freq[a.Last()];
                                var fb = freq[b[0]] + freq[b.Last()];
                                return -(fa.CompareTo(fb));
                            });
        }

        #region Implementation of IForwardStateSpace<State,int>

        public State Decide(State state, Tuple<int, int, int> decision)
        {
            var c = decision.Item1;
            var d = decision.Item2;
            var v = decision.Item3;

            state.UsedValues.Add(v);
            state.G[_words[state.Index].First()] = c;
            state.G[_words[state.Index].Last()] = d;
            state.Index++;
            return state;
        }

        public IEnumerable<Tuple<int, int, int>> Decisions(State state)
        {
            var first = state.Words[state.Index].First();
            var last = state.Words[state.Index].Last();
            int firstFrom, firstTo, lastFrom, lastTo;
            if (state.G.Contains(first))
            {
                firstFrom = state.G[first];
                firstTo = state.G[first] + 1;
            }
            else
            {
                firstFrom = 0;
                firstTo = _maxValue;
            }
            if (state.G.Contains(last))
            {
                lastFrom = state.G[last];
                lastTo = state.G[last] + 1;
            }
            else
            {
                lastFrom = 0;
                lastTo = _maxValue;
            }

            for (int a = firstFrom; a < firstTo; a++)
            {
                for (int b = lastFrom; b < lastTo; b++)
                {
                    var h = _words[state.Index].Length + a + b;
                    var tple = new Tuple<int, int, int>(a, b, h);
                    if (ValueIsPromising(state, tple))
                    {
                        yield return tple;
                    }
                }
            }
        }

        public IEnumerable<State> InitialStates
        {
            get { yield return new State(_words, _maxValue); }
        }

        public bool IsFinal(State state)
        {
            return state.Index == _words.Count;
        }

        #endregion

        #region Implementation of IReversibleForwardStateSpace<State,int>

        public State Undo(State state, Tuple<int, int, int> decision)
        {
            var v = decision.Item3;
            state.Index--;
            var first = _words[state.Index].First();
            var last = _words[state.Index].Last();
            if (!state.FoundChars.Contains(first))
            {
                state.G.Remove(first);
            }
            if (last != first && !state.FoundChars.Contains(last))
            {
                state.G.Remove(last);
            }
            state.UsedValues.Remove(v);
            return state;
        }

        #endregion


        private static bool ValueIsPromising(State state, Tuple<int, int, int> tuple)
        {
            return !state.UsedValues.Contains(tuple.Item3);
        }

        public IEnumerable<KeyValuePair<string, int>> Solution(State finalState)
        {
            foreach (var word in _words)
            {
                var h = word.Length + finalState.G[word[0]] + finalState.G[word.Last()];
                yield return new KeyValuePair<string, int>(word, h);
            }
        }
    }
  

    public class PerfectHashFinder
    {
        private readonly BacktrackingEnumerator<PerfectHashStateSpace3.State, Tuple<int, int, int>, IEnumerable<KeyValuePair<string,int>>> _enumerator;

        public PerfectHashFinder()
        {
            _enumerator =
                new BacktrackingEnumerator<PerfectHashStateSpace3.State, Tuple<int, int, int>, IEnumerable<KeyValuePair<string, int>>>
                    ((space, i, d, f) => ((PerfectHashStateSpace3)space).Solution(f));
        }

        public IEnumerable<KeyValuePair<string,int>> Find(IEnumerable<string> words, int maxValue)
        {
            var space = new PerfectHashStateSpace3(words, maxValue);
            return _enumerator.First(space);
        }
    }

}
